//
// Created by isabella on 25-6-2.
//
#pragma once
#include <common.h>

//抽象排序
class Sort {
public:
    virtual ~Sort() = default;

    virtual vector<int> sort(vector<int>) =0;
};

//冒泡排序
class BubbleSort final : public Sort {
public:
    vector<int> sort(vector<int>) override;
};

//选择排序
class SelectionSort final : public Sort {
public:
    vector<int> sort(vector<int>) override;
};

//快速排序
class QuickSort final : public Sort {
public:
    vector<int> sort(vector<int>) override;

private:
    void doSort(vector<int> &nums, int low, int high);

    int partition(vector<int> &nums, int low, int high);
};

//归并排序
class MergeSort final : public Sort {
public:
    vector<int> sort(vector<int>) override;

private:
    vector<int> merge(vector<int> &nums, int low, int high);
};

//希尔排序-插入排序加强版
class ShellSort final : public Sort {
public:
    vector<int> sort(vector<int>) override;

private:
    void insertionSort(vector<int> &nums, int gap);
};

//堆排序
class HeapSort final : public Sort {
public:
    vector<int> sort(vector<int>) override;

private:
    void sink(vector<int> &nums, int index, int range);

    void heapify(vector<int> &nums);
};

//计数排序
class CountingSort final : public Sort {
public:
    vector<int> sort(vector<int>) override;
};
